import java.util.ArrayList;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-01-02
 * Time: 22:58
 */


public class Solution {
    // 滑动窗口
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> ans=new ArrayList<>();
        int sLen=s.length();
        int pLen=p.length();
        // 如果主串的长度比子串还小, 直接返回
        if(sLen<pLen){
            return ans;
        }
        // 类似于 生产者消费者模型 count数组里面存储的是产品
        int[] count=new int[26];
        // 先设置一个固定的窗口的大小
        for(int i=0;i<pLen;i++){
            // 主串遇到一个字符就加上
            count[s.charAt(i)-'a']++;
            // 子串遇到一个字符就减去
            count[p.charAt(i)-'a']--;
        }
        int differ=0; // 记录不同的 字符 的个数
        for(int i=0;i<26;i++){
            if(count[i]!=0){
                // 遇到不等于0的 说明出现了某个字符的数目不匹配
                differ++;
            }
        }
        if(differ==0){
            // 说明 0 位置就是一个答案
            ans.add(0);
        }
        for(int i=0;i<sLen-pLen;i++){
            // 因为窗口要滑动, 所以要 瞻前顾后, 所以从0开始
            char left=s.charAt(i);// 窗口移动前的首字符
            if(count[left-'a']==1){
                // 窗口左边界后移, 使得某个字符的数目匹配上
                differ--;
            }else if(count[left-'a']==0){
                // 窗口左边界后移, 使得某个字符的数目从匹配变为不匹配
                differ++;
            }
            //将窗口首字符删除
            count[left-'a']--;
            char right=s.charAt(i+pLen);// 窗口移动后的最后一个字符
            if(count[right-'a']==-1){
                // 窗口右边界后移, 使得某个字符的数目匹配上
                differ--;
            }else if(count[right-'a']==0){
                // 窗口右边界后移, 使得某个字符的数目从匹配变为不匹配
                differ++;
            }
            //将移动后的窗口尾字符添加进去
            count[right-'a']++;
            if(differ==0){
                // 窗口移动一个位置之后 变为所有的字符的数目都匹配
                ans.add(i+1);// 记录的是移动过后的起始位置
            }
        }
        return ans;
    }
}
